package sjjg.graph;

import sjjg.tree.IndexMinPriorityQueue;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class PrimMST {
    private Edge[] edgeTo;//索引代表顶点 索引对应的值代表该顶点到最小生成树的最短边
    private double[]distTo;//索引代表顶点 索引对应的值代表该顶点到最小生成树的最短边的权重
    private boolean[]marked;//索引代表顶点 索引对应的值代表该顶点是否处于最小生成树中
    private IndexMinPriorityQueue<Double>pq;//存储横切边
    public PrimMST(EdgeWeightGraph weightGraph){
            if(weightGraph==null){
                return;
            }
            int V=weightGraph.V();
            distTo=new double[V];
        for (int i = 0; i < distTo.length; i++) {
             distTo[i]=Double.MAX_VALUE;//初始让值代表该顶点到最小生成树的最短边的权重最大
        }
            edgeTo=new Edge[V];
            marked=new boolean[V];
            pq=new IndexMinPriorityQueue<>(V);
            //最开始让索引0成为最小生成树的初始节点
            distTo[0]=0.0;
            pq.insert(0,distTo[0]);
            //从队列中取出最小小横切边对应的顶点 将其加入到最小生成树中
            while (!pq.isEmpty()){
                visit(weightGraph,pq.delMin());
            }
    }
    private void visit(EdgeWeightGraph weightGraph,int v){
        marked[v]=true;//将节点v加入最小生成树中
        for (Edge edge : weightGraph.adj[v]) {//更新横切边 及edgeTo distTo
            //如果该权边 对应的两个节点都在生成树中就没必要再遍历了
             if(marked[edge.another(v)]){
                 continue;
             }
            if(edge.weight()<distTo[edge.another(v)]){
                edgeTo[edge.another(v)]=edge;
                distTo[edge.another(v)]=edge.weight();
                if(pq.contains(edge.another(v))){//如过这个索引存在值改变值
                    pq.changeItem(edge.another(v), edge.weight());
                }else {//如过这个索引不存在值插入值
                    pq.insert(edge.another(v),edge.weight());
                }
            }
        }
    }
    public Queue<Edge>edges(){//返回最小生成树的所有边
       Queue<Edge>edges= new LinkedBlockingQueue<>();
        for (Edge edge : edgeTo) {
            if(edge!=null){
                edges.add(edge);
            }
        }
        return edges;
    }
}
